// 当组件的状态或属性变化时，Vue 通过比对新旧虚拟节点（vNode）来找出最小的变化量，并只对实际 DOM 应用这些变化。
// 2. 新旧 vNode 比对流程
// 当需要更新 DOM 时，Vue 会调用 patch 函数来比对新旧 vNode，并应用最小的差异到实际 DOM 中。这个过程主要包括以下步骤：

// a. 比较两个 vNode 是否相同
// 首先，Vue 会检查两个 vNode 是否相同：

// 标签名相同 (sameTag)。
// 都有相同的键 (sameKey)。
// 都是注释节点 (isComment)。
// 如果它们是不同类型的节点，Vue 会替换整个节点；如果它们是相同类型的节点，Vue 会进一步比较它们的子节点和属性。

// b. 更新属性和文本内容
// 如果新旧 vNode 是相同类型的节点，Vue 会更新节点的属性和文本内容。例如：

// 比较 class、style 等属性，并应用差异。
// 如果节点是文本节点，直接更新文本内容。
// c. 比较子节点
// Vue 递归地比较子节点。子节点的比较是 diff 算法的核心部分。它采用了一种高效的双端比较算法：

// 新前与旧前：新节点的前节点与旧节点的前节点比较。
// 新后与旧后：新节点的后节点与旧节点的后节点比较。
// 新后与旧前：新节点的后节点与旧节点的前节点比较。
// 新前与旧后：新节点的前节点与旧节点的后节点比较。
// 这个算法通过尽量减少移动节点的次数来优化性能。

// 4. 总结
// 虚拟节点：描述真实 DOM 结构的 JavaScript 对象。
// diff 算法：通过比较新旧 vNode，找出最小的变化量，并应用到实际 DOM。
// 双端比较：高效的子节点比较算法，通过减少 移动次数优化性能。

// 1. 排序算法
// a. 冒泡排序
// 冒泡排序是最简单的排序算法之一。它通过重复地遍历要排序的列表，比较相邻的元素并根据需要交换它们的位置来排序列表。

// javascript
// 复制代码
// function bubbleSort(arr) {
//   let n = arr.length;
//   for (let i = 0; i < n - 1; i++) {
//     for (let j = 0; j < n - 1 - i; j++) {
//       if (arr[j] > arr[j + 1]) {
//         [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 交换
//       }
//     }
//   }
//   return arr;
// }

// const arr = [5, 3, 8, 4, 2];
// console.log(bubbleSort(arr)); // [2, 3, 4, 5, 8]
// b. 快速排序
// 快速排序是一种效率较高的排序算法，它使用分治法将数组分为较小的子数组，然后递归地排序这些子数组。

// javascript
// 复制代码
// function quickSort(arr) {
//   if (arr.length <= 1) return arr;

//   let pivot = arr[Math.floor(arr.length / 2)];
//   let left = [];
//   let right = [];

//   for (let i = 0; i < arr.length; i++) {
//     if (i === Math.floor(arr.length / 2)) continue;
//     if (arr[i] < pivot) {
//       left.push(arr[i]);
//     } else {
//       right.push(arr[i]);
//     }
//   }

//   return [...quickSort(left), pivot, ...quickSort(right)];
// }

// const arr = [5, 3, 8, 4, 2];
// console.log(quickSort(arr)); // [2, 3, 4, 5, 8]
// 2. 查找算法
// a. 二分查找
// 二分查找是一种在有序数组中查找元素的高效算法。它通过反复将搜索范围减半来缩小查找范围。

// javascript
// 复制代码
// function binarySearch(arr, target) {
//   let left = 0;
//   let right = arr.length - 1;

//   while (left <= right) {
//     let mid = Math.floor((left + right) / 2);
//     if (arr[mid] === target) {
//       return mid;
//     } else if (arr[mid] < target) {
//       left = mid + 1;
//     } else {
//       right = mid - 1;
//     }
//   }

//   return -1; // 未找到
// }

// const arr = [2, 3, 4, 5, 8];
// console.log(binarySearch(arr, 4)); // 2
// console.log(binarySearch(arr, 7)); // -1
// 3. 动态规划
// a. 斐波那契数列
// 动态规划是一种通过将问题分解为子问题来解决问题的算法。斐波那契数列是动态规划的经典例子。

// javascript
// 复制代码
// function fibonacci(n) {
//   let dp = [0, 1];
//   for (let i = 2; i <= n; i++) {
//     dp[i] = dp[i - 1] + dp[i - 2];
//   }
//   return dp[n];
// }

// console.log(fibonacci(6)); // 8
// 4. 其他常用算法
// a. 去重
// 去重是指从数组中移除重复的元素。

// javascript
// 复制代码
// function unique(arr) {
//   return [...new Set(arr)];
// }

// const arr = [1, 2, 3, 4, 3, 2, 1];
// console.log(unique(arr)); // [1, 2, 3, 4]
// b. 洗牌算法
// 洗牌算法用于随机打乱数组顺序。

// javascript
// 复制代码
// function shuffle(arr) {
//   for (let i = arr.length - 1; i > 0; i--) {
//     let j = Math.floor(Math.random() * (i + 1));
//     [arr[i], arr[j]] = [arr[j], arr[i]];
//   }
//   return arr;
// }

// const arr = [1, 2, 3, 4, 5];
// console.log(shuffle(arr)); // 打乱后的数组，例如 [3, 1, 4, 5, 2]
// 5. 数组扁平化
// 数组扁平化是指将多维数组转换为一维数组。

// javascript
// 复制代码
// function flatten(arr) {
//   return arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatten(val) : val), []);
// }

// const arr = [1, [2, [3, 4], 5], 6];
// console.log(flatten(arr)); // [1, 2, 3, 4, 5, 6]
// 这些算法都是前端开发中非常实用的基本算法。理解并掌握这些算法能够帮助你在解决实际问题时更加高效。
export function patch(oldVnode, vnode) {
  console.log(
    oldVnode,
    vnode,
    oldVnode && oldVnode.nodeType,
    "diff--path--oldVnode--vnode---组件化",
  );
  //自定义组件 此时 oldVnode是有值的
  //第一次渲染的时候 oldVnode是一个真实的dom   组件的挂载 vm.$el 对应的就是组件的渲染结果了
  // 组件的挂载 vm.$el 对应的就是组件的渲染结果了
  if (!oldVnode) return createEl(vnode);
  const isRealElement = oldVnode.nodeType;
  console.log(isRealElement, "diff--isRealElementisRealElement");
  //0. oldVnode是一个真实的dom情况
  if (isRealElement) {
    //实现： vnode ===> 变成真实dom
    //1. 创建新DOM
    let el = createEl(vnode);
    console.log(el, "el-elelel-new");
    //2. 替换 2.1获取父节点 2.2新的节点插入 2.3删除旧的
    // document.body.replaceChild(el, oldVnode);  insertBefore 方法用于在指定节点的前面插入一个新的子节点。它接受两个参数，第一个参数是要插入的节点，第二个参数是参考节点，即新节点将被插入到这个节点之前
    // nextSibling 属性：nextSibling 是一个只读属性，用于访问同级节点中的下一个节点。如果没有下一个节点，则返回 null
    let praentEl = oldVnode.parentNode; //body
    praentEl.insertBefore(el, oldVnode.nextSibling); //在老dom下的第一个兄弟之前插入
    praentEl.removeChild(oldVnode); //删除老的dom
    return el; //返回最新的el
  } else {
    // 0.获取老的el dom进行 增加 删除 替换等功能--实现最小的变动，diff算法
    vnode.el = oldVnode.el; //在原来的el上进行 新增 ，删除，修改等操作---》最后以最小的变动生成最新的dom
    const el = oldVnode.el;

    // ------------------- 更新节点 --------------------
    /**
     * 直接将新节点替换老节点，很消耗性能
     * 所以我们不直接替换，而是在比较两个节点之间的区别之后在替换，这就是diff算法
     * diff算是 是一个平级比较的过程，父亲和父亲节点比对 儿子和儿子节点比对
     */
    /**
     * 1. 两个节点不是同一个节点，直接删除老的换上新的（不在继续对比属性等）
     * 2. 两个节点是同一个节点（tag，key都一致），比较两个节点的属性是否有差异
     * 复用老节点，将差异的属性更新
     */
    console.log("diff--vnode使用patch方法更新了");
    //1. 元素不一样
    if (oldVnode.tag !== vnode.tag) {
      return oldVnode.el.parentElement.replaceChild(
        createEl(vnode),
        oldVnode.el,
      ); //停止向下继续判断
    }
    // 2. 标签一样  文本 属性 <div>1</div> <div>2</div> tag: undefined
    if (!oldVnode.tag) {
      // 文本内容 发生变动 1  变成了 2
      if (oldVnode.text !== vnode.text) {
        return (el.textContent = vnode.text);
      }
    }

    // 2.1 属性
    // 新旧属性进行对比操作
    updateRports(vnode, oldVnode.data);

    //3.
    // 最后，判断是否存在子集，递归子集，重新走上面的逻辑
    // diff 处理子元素
    // 1. 老的元素 有儿子 新的元素有儿子
    // 2. 老的元素 有儿子 新的元素没有儿子
    // 3. 老的元素 没有儿子 新的元素 有儿子
    let oldChildren = oldVnode.children || [];
    let newChildren = vnode.children || [];
    if (oldChildren.length && newChildren.length) {
      // 1. 老的元素 有儿子 新的元素有儿子
      // 创建一个方法  双指针比对
      console.log("diff--1111");
      updateChild(oldChildren, newChildren, el); // 老的真是el dom进行更新
    } else if (oldChildren.length) {
      // 2. 老的元素 有儿子 新的元素没有儿子
      el.innerHTML = "";
      console.log("diff--2222");
    } else if (newChildren.length) {
      // 3. 老的元素 没有儿子 新的元素 有儿子
      console.log("diff--3333");
      for (let i = 0; i < newChildren.length; i++) {
        let child = newChildren[i];
        // 向老dom 添加子 dom内容
        el.appendChild(createEl(child));
      }
    }
  }
}

// 1.0 抽取的方法 (老的有儿子 新的有儿子)如何比对
function updateChild(oldChildren, newChildren, el) {
  console.log(
    oldChildren,
    newChildren,
    el,
    "updateChild-老的儿子和新的儿子比对",
  );
  // vue diff算法 做了很多优化 <li>1</li> <li>2</li>
  // dom 中操作元素===》 常用的逻辑 尾部添加 头部添加 倒叙和正序的方式
  // vue2 双指针  思想
  // 图如下
  // old:  A     B   C
  // new:  A     B   C  D

  //0.1 创建双指针
  let oldStartIndex = 0; // 老的开始索引
  let oldStartVnode = oldChildren[oldStartIndex]; // 老的开始元素
  let oldEndIndex = oldChildren.length - 1; // 老的结尾索引
  let oldEndVnode = oldChildren[oldEndIndex]; // 老的结尾元素
  let newStartIndex = 0; // 新的开始索引
  let newStartVnode = newChildren[newStartIndex]; // 新的开始元素
  let newEndIndex = newChildren.length - 1; // 新的结尾索引
  let newEndVnode = newChildren[newEndIndex]; // 新的结尾元素
  // 判断 两个虚拟dom是不是 同一个---声明方法
  function isSomeVnode(oldVnode, newVnode) {
    return oldVnode.tag === newVnode.tag && oldVnode.key == newVnode.key;
  }
  //
  /**
   * 生成映射表----生成key 和 索引的 映射表对象
   * @param {*} children
   * @returns
   */
  function makeIndexByKey(children) {
    const map = {};
    children.forEach((child, index) => {
      if (child.key) {
        map[child.key] = index;
      }
    });
    return map;
  }
  //1.0 创建旧元素的映射表
  // 乱序比较时 使用的映射表 {key:"节点在数组中的索引"} -> {a:0,b:1,...},首先生成老children的映射表
  const oldChildVnodeKeyIndexMap = makeIndexByKey(oldChildren);
  // a:遍历
  while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
    // a:新前与旧前 比对子元素
    //a:头部 注意 头部这个虚拟dom是不是同一个元素
    if (isSomeVnode(oldStartVnode, newStartVnode)) {
      // a b c ===> a b c d
      // 表示是 旧的虚拟dom第一个元素 和新虚拟dom中第一个元素 是同一个元素
      // 继续递归 因为他里面可能也有子元素 如文本，如p,div元素标签
      patch(oldStartVnode, newStartVnode);
      // 然后移动指针 更新老的开始元素 和新的开始元素 继续进行比对
      oldStartIndex = oldStartIndex + 1;
      oldStartVnode = oldChildren[oldStartIndex];
      newStartIndex = newStartIndex + 1;
      newStartVnode = newChildren[newStartIndex];
    } else if (isSomeVnode(oldEndVnode, newEndVnode)) {
      // 新后和旧后 比对如果 a b c  ====> d a b c   新节点比旧节点多
      //                    d a b c ===> a b c                        旧节点比新节点多
      patch(oldEndVnode, newEndVnode); //递归
      // 继续更新 新后指针 旧后指针 以及 更新--新尾数据和旧尾部数据
      newEndIndex = newEndIndex - 1;
      newEndVnode = newChildren[newEndIndex];
      oldEndIndex = oldEndIndex - 1;
      oldEndVnode = oldChildren[oldEndIndex];
    } else if (isSomeVnode(oldEndVnode, newStartVnode)) {
      //交叉比较  ===》  //交叉比较  ===》 //交叉比较  ===》 //交叉比较  ===》新前 / 旧后
      // a  b  c ==> b  c  a===> 头比较 不满足  尾比较不满足 上方两条件
      // 递归
      patch(oldEndVnode, newStartVnode);
      // 新前指针 前移  旧后指针后移
      // 并且更新新的 新前vnode 和 旧后vnode继续判断 是否一样
      newStartIndex = newStartIndex + 1;
      newStartVnode = newChildren[newStartIndex];
      oldEndIndex = oldEndIndex - 1;
      oldEndVnode = oldChildren[oldEndIndex];
    } else if (isSomeVnode(newEndVnode, oldStartVnode)) {
      //交叉比较  ===》 //交叉比较  ===》 //交叉比较  ===》 //交叉比较  ===》
      // 新后 / 旧前
      patch(oldStartVnode, newEndVnode); //递归
      oldStartIndex = oldStartIndex + 1;
      oldStartVnode = oldChildren[oldStartIndex];
      newEndIndex = newEndIndex - 1;
      newEndVnode = newChildren[newEndIndex];
    } else {
      //暴力比对 儿子vnode之间没有任何关系====》思路
      //1.0 创建旧元素的映射表
      //2.0 根据老的列表做一个映射关系，用新的去找，找到则移动节点，找不到就新增节点，最后移除多余节点
      // 在老的dom上 进行 更新--最终以最小的变动获取最新的dom
      //----每次经过上方 三种比对方法之后，都没有满足条件的，那么新vnode插入到老vnode第一个元素的之前，然后在移动新index继续 找上方三种比对方法，还是没有满足的，继续在老vnode的第一个元素的最前面插入
      // 乱序比对 a b f c ->  g e f d m
      /**
       * 根据老的列表做一个映射关系，用新的去找，找到则移动节点，找不到就新增节点，最后移除多余节点
       *  {a: 0, b: 1, c: 2}
       */
      // 如有值：则是需要移动的节点的索引
      let moveIndex = oldChildVnodeKeyIndexMap[newStartVnode.key];
      console.log(
        oldChildVnodeKeyIndexMap,
        moveIndex,
        newStartVnode,
        newChildren,
        newStartIndex,
        "diff--moveIndex",
      );
      console.log("%c乱序比对 a b f c ->  g e f d m", "color: blue");
      if (moveIndex != undefined) {
        // 在老的映射表中找到了--那么复用老的节点
        console.log(
          "在老的映射表中找到找到了了了--el,oldStartVnode",
          el,
          oldStartVnode,
        );
        let moveNode = oldChildren[moveIndex]; //获取到移动的元素
        // 标识这个节点已经移动过
        oldChildren[moveIndex] = undefined; // 把找到的老的元素移出去之后，防止老的节点数组塌陷
        // 插入 移动节点到头指针所在老的节点的前面
        el.insertBefore(moveNode.el, oldStartVnode.el);
        // 插入的元素 又有儿子 递归
        patch(moveNode, newStartVnode); //继续比对子元素
      } else {
        // 在老的映射表中没有找到
        console.log(
          "在老的映射表中没有找到--el,oldStartVnode",
          el,
          oldStartVnode,
        );
        el.insertBefore(createEl(newStartVnode), oldStartVnode.el);
      }

      //新的元素指针位移  最后一定要更新  新节点开始节点 索引和 开头元素 循环执行下去
      newStartIndex = newStartIndex + 1;
      newStartVnode = newChildren[newStartIndex];
    }

    // 面试题 为什么要添加key  这个key值不能是index  索引，，，只是作为渲染没有问题  修改了 比如删除 修改等
    // <li key="0"> 桃子</li>
    // <li key="1"> 西瓜</li>
    // <li key="2"> 香蕉</li>

    // <li key="0"> 香蕉</li> // 如果用索引 那么就会新旧dom进行比对的 双指针比对 头部比对中会去创建 新的香蕉这个子节点到dom上，复用效率低，如果是id的话通过 交叉比较 找到香蕉这个虚拟dom，发现你key相同那么就会复用这个dom，效率高,,,,位移
    // <li key="1"> 西瓜</li>
    // <li key="2"> 桃子</li>
  }
  // c  b  a   ====> f  g  e  a  完整版本 测试上方diff算法    ====》diff算法完成
  console.log(
    oldStartIndex,
    oldEndIndex,
    newStartIndex,
    newEndIndex,
    "oldStartIndex,oldEndIndex,newStartIndex,newEndIndex",
  );

  // insertBefore 方法是 DOM API 中的一个常用方法，用于在指定的父节点中将某个新节点插入到一个现有子节点之前。如果该现有子节点为 null，则将新节点追加到父节点的末尾。
  // 循环完了添加多余的儿子 旧的oldEndIndex 最大值是2  newEndIndex最大值是5 说明中间有三个是新的元素
  // 新节点的比旧节点多处理
  if (newStartIndex <= newEndIndex) {
    // 新前和旧前 比对结果
    // 这里可能是向后追加 也可能是向前插入
    for (let i = newStartIndex; i <= newEndIndex; i++) {
      // 父元素去追加这些新的 dom元素
      const anchor = newChildren[newEndIndex + 1];
      if (anchor) {
        // 表示向前插入--新后和旧后比对结果
        console.log(el, anchor, "新节点比旧节点多情况--向前插入--anchor");
        // 老的dom 通过父元素节点 将新节点d添加到 老dom,a和doma的位置是一样的，他的前面添加d
        el.insertBefore(createEl(newChildren[i]), anchor.el);
      } else {
        console.log(el, "新节点比旧节点多情况--向后添加---");
        // 老的dom 通过父元素节点 尾部appendChild追加
        el.insertBefore(createEl(newChildren[i]), null);
      }
    }
  }
  //旧节点比新节点多处理
  if (oldStartIndex <= oldEndIndex) {
    for (let i = oldStartIndex; i <= oldEndIndex; i++) {
      // 对多出的老节点进行移除
      console.log(el, oldChildren[i], "el--对多出的老节点进行移除");
      oldChildren[i] && el.removeChild(oldChildren[i].el);
    }
  }
}

// 添加属性
function updateRports(vnode, oldProps = {}) {
  let newProps = vnode.data || {}; // 获取当前新节点的属性
  let el = vnode.el; // 获取当前真实的节点 {}
  console.log(newProps, oldProps, vnode, "diff--newProps, oldProps,vnode");
  //编辑：
  //0.1 老的有属性 新的没有属性 那么进行删除新dom上之前老的属性 来更新-新dom上的属性
  for (let key in oldProps) {
    if (!newProps[key]) {
      console.log(key, "删除老的样式属性key,因为新dom上没有改属性了");
      // 删除属性
      el && el.removeAttribute(key);
    }
  }
  //0.2情况 老的 style = {color: 'red'}  新的 style = {background: red}
  let newStyle = newProps.style; //获取新属性中的style内联样式
  let oldStyle = oldProps.style; //获取老属性中的style内联样式
  for (let key in oldStyle) {
    // 如果在编辑老属性的时候，发现新数据中没有这个key,
    // 那么操作新的dom上去删除这个老的属性key,来达到更新。
    if (!newStyle[key] && el) {
      el.style = "";
    }
  }

  //新增： 第一次标签没有属性的时候，进行dom上添加属性
  // 新dom上新添加的属性 老的dom上没有的属性情况
  for (let key in newProps) {
    console.log(key, "diff--属性key");
    if (key == "style") {
      // 处理style

      for (let styleName in newProps.style) {
        if (!el) return;
        el.style[styleName] = newProps.style[styleName];
      }
    } else if (key == "class") {
      if (!el) return;
      // 处理class
      el.className = newProps.class;
    } else {
      // 处理普通属性

      el && el.setAttribute(key, newProps[key]);
    }
  }
}

// 根据最新的vNode ===>声明创新dom方法==该方法的作用是把vnode变成真实的dom
export function createEl(vnode) {
  // vnode: {tag,text,data,children}
  let { tag, text, data, key, children } = vnode;

  if (typeof tag == "string") {
    // 注意  标签 可能是 html标签  或者 自定义的组件标签
    if (crateComponent(vnode)) {
      // 自定义写的组件   然后将自定义组件的vnode转换真实dom
      console.log(vnode,'组件化--最后最后的最后-创建自定义组件dom成功之后')
      return vnode.componentInstance.$el;
    } else {
      // html标签 将html的vnode创建真实dom
      // 判断是不是标签，存在标签，创建标签
      // 以下是原生js操作 创建dom 放到页面进行渲染
      vnode.el = document.createElement(tag); // 创建元素

      // 初始化第一次调用的时候向dom添加属性
      updateRports(vnode);
      // 递归处理子集 children []，追加子集
      if (children.length) {
        children.forEach((child) => {
          //递归 vnode.el ==》父元素 createEl(item) ==》子元素
          console.log(child, vnode.el, tag, "2024-8-14");
          vnode.el.appendChild(createEl(child));
        });
      }
    }
  } else {
    // 创建文本
    vnode.el = document.createTextNode(text);
  }

  return vnode.el;
}

//自定义组件：：： 根据vnode更新真实dom
function crateComponent(vnode) {
  let i = vnode.data; //调用声明的组件 初始化方法 init
  if ((i = i.hook) && (i = i.init)) {
    console.log(i, "组件化---自定义组件逻辑");
    i(vnode); // init(vnode) 调用之后 创建一个子组件的实例
  }

  // 判断有没有 已经创建子组件的实例
  if (vnode.componentInstance) {
    return true; //表示 已经存在子组件的 实例----可以继续进行 挂载到页面上了
  } else {
    return false;
  }
}

//总结:面试题
//  vue的渲染流程==》数据初始化==》对模板进行编译==》变成render函数（ast语法树==》render函数字符串==》render函数）==》render函数变成vnode==>vnode变成真实dom==>放到页面上
